Cache Invalidation

Consistency — it is not possible to read a stale value. Every read is guaranteed to read the latest data.

Inconsistent – it is possible for the reads to be stale (possible for us to read an old value)

Immediate Consistency — data will immediately be consistent. No waiting required. All copies sync up immediately. Impossible to read a stale/old value.

Eventual Consistency — data will be consistent eventually. For some time, the data might be inconsistent, but if you wait long enough, then it will become consistent (everything will sync up eventually)

No Consistency — data loss can happen! No matter how long you wait, your data will never become consistent.

More about consistency in future classes.

How cache reads/writes happen

typical read/write cycle

1. Write requests go directly to the database (typically)

• not to the cache

2. Read request

• first app servers checks if the value is in the cache
• if present (Cache Hit)

1. return the cached value

• if not present (Cache Miss)

1. app server fetches value from DB
2. returns to the user
3. (async) updates the value in the cache

Why doesn't the cache automatically fetch the data from the DB in case of a cache miss?

Separation of concerns. Business logic required to fetch data (auth / sorting / filtering / ...) resides in the app server - it is a bad idea to have the same business logic in multiple places.

Q: why can’t we update the cache & the database together for each write?

because it’s hard & slow — more on this later

When we do something like this, it is called a Write Through cache.

Q: Can the cache itself fetch the data from the database?

Why does a cache miss have to happen in the above manner?

If the cache doesn’t have some data, can’t it itself fetch it from the database, store it, and then return it to the app server?

disclaimer: some people do it, but it is typically considered bad design (anti-pattern)

Reason: separation of concerns

1. business logic (what data to fetch, what tables to join, how to filter the data, how to validate it, how to sort it).. all of this lives inside the app server.
2. Cache server is supposed to be “dumb”
3. If we try to make the cache server intelligent, then our business logic will be split across two entities - app server & cache server

• what if the two codebases are not in sync?

• codebase logic can be stale in some place

• cache server has to have a powerful CPU — to do all this slicing & dicing of data

Therefore, any fetching/updating responsibilities lies with the app server. Cache server just acts as dumb-storage.

Note: since any writes only go the DB, the data inside the cache can get stale

If a read now comes to the cache, the cache will tell you happily that the value is 10 — which is incorrect!

Note that because this will be a cache hit, the app-server will just return this incorrect value to the client — it won’t even check the database.

Time to Live (TTL)

note: you might also see TTL be called a cache eviction strategy — it is both an invalidation policy and an eviction policy (because it is so simple, but with a little modification. Pure TTL is NOT an eviction policy)

Whenever you store data inside cache, apart from storing the value, you also store the expiry time.

Every cache entry has a fixed amount of time for which it is valid (TTL).

TTL can be configured globally (for all keys), or it can be configured per key as well.

After the TTL expires, we assume that the value is stale, and we invalidate it.

In reality, we have no idea whether the value is actually stale or not (whether the value has been updated in the database or not)

For example, if we write a=10 to the cache at 8am, and our TTL is 1 hour, then the expiry for this entry will be set to 8am + 1 hour = 9am

Q: When do we actually delete this entry from the cache?

Do we delete it

1. Eager Invalidation: Immediately when the expiry happens?

1. This would mean that our cache server has to run some sort of an event loop / timer for each expiry. (Timer + Priority Queue)
2. Additional overhead in the cache server.

1. Imagine if for some reason a lot of entries have the same expiry time (say 9am)
2. Then at 9am, any request that comes will have to wait because the cache server will be busy clearing up all the expired entries.
3. Performance will be “jittery” – it will not be smooth.
4. Because of this cleanup process, there can be temporary latency increases in the cache performance
   

2. Lazy Invalidation: When the next read request comes?

1. If we do this, then we’re potentially storing state data in the cache — wastage of space
2. But that isn’t an issue, because the eviction algo is taking care of that.
3. Always better to invalidate in a lazy manner — this will give you a smooth latency over all requests

Q: What sort of consistency does TTL invalidation provide?

Q: Can the data served from the cache be stale?

What if we read stale data from the cache, before the value has a chance to expire?

Yes, if an update happens in the database before the cache entry expires, then the subsequent reads (before expiry) will return the stale data from the cache.

So, TTL provides "eventual consistency"

Note: when the read request (after update) came, we first checked the cache (as we always do). Since we found the data in the cache, and the data had not expired (even though it was stale), we returned it to the user. We ended up serving stale data.

Q: What’s the ideal value for TTL?

Completely dependent on the application.

It might be as low as 5 seconds, or it might be as large as a week.

The lower the TTL is, the more cache “misses” you will have, because the data will be invalidated very quickly. But at the same time, your data will be “more fresh”

The higher the TTL, the better your cache hit rate will be. But at the same time, you data will be “more stale”.

Q: Can we update the expiry of an entry every time we access it from the cache?

No, we should not do that when the read requests come

Imagine that the initial set in cache was done at 8.55 with expiry set to 9

An update was made in DB at 8.58, so the cache is now stale. And the cache will be invalidated at 9

If a read request comes at 8.59, and you move the expiry forward to 9.05, in this case your TTL is now higher — your data will remain stale until 9.05

We can push the expiry forward when we write to the cache, but then, it is not really TTL — it becomes something else entirely.

Analogy for TTL

Imagine that you’re storing some fruits in your fridge..

TTL

1. whenever you purchase fruits from the market, before you put them in the fridge, you will label each individual fruit with an expiry date.
2. when you’re hungry, you will just check the fridge for the fruit that you want to eat
3. you will check the tag

• if the expiry date on the tag has passed

• then you will throw that fruit in the garbage

• even though the fruit actually doesn’t look spoilt

• and you will go to the market to purchase it

• if the expiry date has not passed, then you will eat the fruit

• even if the fruit is rotten

Write Around

very similar to TTL - as in it also provides "eventual consistency"

Key differences (compared to TTL)

1. TTL: works best when fetching an entry from the DB is easy, or requires no additional postprocessing/computation
   
   user_preferences
   user_id (bigint)    name (text)   preferences (json)
   
   select * from user_preferences
   where user_id = 1234
   
   Very simple & fast query.
   Assume that we need to cache the user preferences and we’re okay with eventual consistency, then, the ideal invalidation policy will be TTL.
   
2. Write Around: works best when fetching data from the DB is extremely expensive, or requires additional postprocessing/computation

• we will see example of this in the case study

user_preferences
user_id (bigint)    name (text)   preferences (json)

Find out all the users that are using dark theme on some mobile device.

select * from user_preferences up
join user_devices ud on ud.user_id = up.user_id
where ud.device_type = ‘mobile’ and up.theme = ‘dark’
group by up.user_id

Complex & slow query.
In this case, it might be better to use a Write Around policy.

In case of write around, there's a separate background process (running in a separate app server) that periodically fetches all recently updated data from DB, does the computation, and updates the cache in one go.

select * from ...

where updated_at > (now() - "1 hour")

Q: Can Write Around serve stale data from the cache?

Yes. Until the background "cron job" runs again, any updates to the db means that the cache has stale data.

Analogy for write around

Imagine that you’re storing some fruits in your fridge..

Write Around

• whenever you purchase fruits from the market, you just put them in the fridge

• you only go to the market at random times

• whenever you want to eat the fruit, you check your fridge

• if the fruit is there, you eat it

• irrespective of whether it is fresh or rotten

• if the fruit is not there, you sleep hungry

• you don’t go to the market

• every weekend you simply throw out all the fruits from your fridge

• irrespective of whether they’re fresh or rotten
• and you restock your fridge

Q: If the data is not found in the cache (the cron job has not even run once so far), then what happens during a read?

Reads always check the cache. If the data is not in the cache, we simply return a 404 error to the client. We do NOT go to the database.

Why?

Because we use write-around when the data fetching/computation is expensive.

So if the computed data is not found in the cache, we want to wait for the computation to complete once, instead of doing the computation on the fly for each incoming request.

Q: What if the data is too large to fit in the cache?

Write-around is typically done when the “computed” data is small enough to fit in the cache.

Eviction algorithm is usually not needed for the data that will be cached. You will evict it only when the data is no longer required.

For example, when the contest is over, you can evict the leaderboard data.

Write Through

In certain cases, we require "immediate consistency" (aka strong consistency) (no stale reads, ever)

The only way to achieve that is to ensure that whatever writes happen, happen at both the cache and the db together!

Write through cache is difficult - because ensuring atomicity across multiple servers is difficult!

Single Server

1. OS - thread synchronization (locks, semaphores, mutexes.. )
2. Shared RAM
3. It is easy to ensure that two tasks happen atomically (either both, or neither)

Multiple Servers (cache & db)

1. No shared RAM
2. what if the write to DB succeeds but the write to the cache fails?

1. either retry the write to cache (user will have to wait – high latency)
2. or, rollback the DB write (transactions)

3. what if the write to DB succeeds, the write to cache succeeds, but the response from the cache fails?

1. app server thinks that the write failed somewhere, so it will try to rollback/retry

4. what if the rollback fails
5. what if the ACK for the rollback fails?

2 Phase Commit - protocol used to perform atomic transactions in a distributed setting

• slow (high latency & low throughput)
• hard to implement (needs state management)
• needs additional infrastructure

We will formalize this trade-off in the CAP theorem class.

If you want consistency, you have to pay for it in blood (it will cause high latency and low throughput)

Optional Readings

1. Theory: Distributed Systems 7.1: Two-phase commit
2. Explanation 1: Distributed Transactions are Hard (How Two-Phase Commit works)
3. Explanation 2: Distributed Transactions: Two-Phase Commit Protocol
4. Implementation: Implementing Distributed Transactions using Two Phase Commit Protocol

Note:

• 2 phase commit is needed only in the case of global cache

• the app server has to make writes in 2 place — db & cache

• if the cache is local, you will ALWAYS use immediate consistency (write through) if the writes come to the app servers.

• no latency issues, no 2PC required
• Because the cache is "local" (RAM/HDD) and it is guaranteed that writes always succeed.
• effectively only have to coordinate with the database write (no need of managing 2 states)

Write Back

It provides no consistency guarantees. In fact, write back cache can lead to Data Loss!

Writes do NOT go to the database - instead, writes go to the cache

Periodically, you write the data back from the cache to the database

Q: How can there be data loss?

Yes, this can lead to data loss!

If the cache server crashes with unsynced changes, then the data is permanently lost.

• cache is volatile, it doesn't store data on disk
• DB is persistent, but the cache server crashed with new data that had not been synced in the db yet

Q: Why would we ever use it?

Pros:

1. Any read/write is happening at cache
2. Any read/write will be insanely fast! (100,000+ reads/writes per second)

• compared to a database which can only handle 100 to 1000 writes/second per server

In scenarios where

• the individual data points are not important

• when it is okay to lose some data
• when trends matter more than individual data points
• analytics
  
• examples: tracking the number of views/likes/clicks on a video/post/...

• extremely high write throughput is required

Cache Eviction

If you’ve just started the cache server, it is initially empty.

Do you want your cache server to be empty?

No! You want the cache to be full, because otherwise you’re wasting much-needed cache. You want to cache as much data as possible!

As the operations continue, the cache server will get full — it will always remain full from this point onwards (unless it crashes & restarts)

But, you still want to cache more data into it (even though it is full) — this means, you first have to get rid of something that is already cached to make space for new data.

Cache Eviction algorithm decides which data to “kick-out” to make space for new data.

How do you decide which eviction policy to use?

1. just use LRU

• no need to think at all — LRU works well for all usecases
• it might not be the perfect choice, but it will work well enough

2. only if you've a lot of extra time, and you've already optimized everything else

• you can implement and run all the various eviction strategies
• measure which one is performing the best in practice
• (never guess)

First in First Out (FIFO)

Last in First Out (LIFO)

Least Recently Used (LRU)

99% cases

H/W: read about

1. temporal locality of data

• if some data has been accessed right now, then it is highly likely, that it will access again in the near future

2. spatial locality of data

• if some data has been accessed right now, then it is highly likely, that “nearby” data will be accessed in the near future
• [a, b, c, d, f, e, g, r, …]

Least Frequently Used (LFU)

Most Recently Used (MRU)

Complete opposite of LRU.

Bad for 99% cases!

H/W: find a valid use-case of the MRU eviction policy